#include <stdio.h>
#include <stdlib.h>

typedef enum { false, true } bool;
typedef int Vertex; /* 顶点编号类型 */
typedef int GElemSet; /* 边权重类型 */
typedef char VertInfo; /* 顶点信息类型 */
typedef struct MGraphNode *MGraph; /* 邻接矩阵表示的图 */
struct MGraphNode {
    int n_verts; /* 顶点数 */
    int m_edges; /* 边数 */
    GElemSet **edge_matrix;/* 邻接矩阵 */
    VertInfo *ver_list; /* 存储顶点信息 */
    GElemSet no_edge_value; /* 表述没有边时的权重值 */
    bool directed; /* true为有向图，false为无向图 */
};
#define NIL -1 /* 顶点不存在时的返回值 */

void InitGraph(MGraph graph, int kMaxVertex, GElemSet no_edge_value,
               bool directed);
int NumberOfVerts(MGraph graph);
bool ExistEdge(MGraph graph, Vertex u, Vertex v);
Vertex FirstAdjVert(MGraph graph, Vertex v);
void InsertEdge(MGraph graph, Vertex u, Vertex v, GElemSet weight);
void RemoveEdge(MGraph graph, Vertex u, Vertex v);
void RemoveVert(MGraph graph, Vertex v);

MGraph BuildGraph() {
    MGraph graph;
    int kMaxVertex, n, m, i;
    Vertex u, v;
    GElemSet weight, no_edge_value;

    scanf("%d %d\n", &kMaxVertex, &no_edge_value);
    graph = (MGraph)malloc(sizeof(struct MGraphNode));
    InitGraph(graph, kMaxVertex, no_edge_value, true);
    scanf("%d %d\n", &n, &m);
    for (v = 0; v < n; v++) {
        scanf("%c ", &graph->ver_list[v]);
        graph->n_verts++;
    }
    for (i = 0; i < m; i++) {
        scanf("%d %d %d\n", &u, &v, &weight);
        InsertEdge(graph, u, v, weight);
    }
    return graph;
}

int main(void) {
    MGraph graph;
    Vertex u, v;

    graph = BuildGraph();
    printf("邻接矩阵为：\n");
    for (u = 0; u < graph->n_verts; u++) {
        for (v = 0; v < graph->n_verts; v++) {
            printf("%d ", graph->edge_matrix[u][v]);
        }
        printf("\n");
    }
    printf("顶点数 = %d\n", NumberOfVerts(graph));
    scanf("%d %d\n", &u, &v);
    printf("<%d, %d> 的存在性 = %d\n", u, v, ExistEdge(graph, u, v));
    scanf("%d %d\n", &u, &v);
    printf("<%d, %d> 的存在性 = %d\n", u, v, ExistEdge(graph, u, v));
    scanf("%d\n", &v);
    printf("顶点%d的第一个邻接点 = %d\n", v, FirstAdjVert(graph, v));
    scanf("%d %d\n", &u, &v);
    RemoveEdge(graph, u, v);
    printf("<%d, %d> 的存在性 = %d\n", u, v, ExistEdge(graph, u, v));
    scanf("%d\n", &v);
    printf("待删除的顶点信息为 %c\n", graph->ver_list[v]);
    RemoveVert(graph, v);
    printf("当前顶点数 = %d\n", graph->n_verts);
    printf("当前边数 = %d\n", graph->m_edges);
    for (v = 0; v < graph->n_verts; v++) {
        printf("%c", graph->ver_list[v]);
    }
    printf("\n");
    printf("邻接矩阵为：\n");
    for (u = 0; u < graph->n_verts; u++) {
        for (v = 0; v < graph->n_verts; v++) {
            printf("%d ", graph->edge_matrix[u][v]);
        }
        printf("\n");
    }
    return 0;
}

void InitGraph(MGraph graph, int kMaxVertex, GElemSet no_edge_value,
               bool directed) {
    /* 初始化一个空的图 */
    GElemSet *array;
    int i;
    Vertex u, v;

    graph->n_verts = 0;
    graph->m_edges = 0;
    /* 声明二维数组graph->edge_matrix[kMaxVertex][kMaxVertex] */
    array = (GElemSet *)malloc(sizeof(GElemSet) * kMaxVertex * kMaxVertex);
    graph->edge_matrix = (GElemSet **)malloc(sizeof(GElemSet *) * kMaxVertex);
    for (i = 0; i < kMaxVertex; i++) {
        graph->edge_matrix[i] = &array[i * kMaxVertex];
    }
    /* 声明顶点信息数组graph->ver_list[kMaxVertex] */
    graph->ver_list = (VertInfo *)malloc(sizeof(VertInfo) * kMaxVertex);
    graph->no_edge_value = no_edge_value;
    graph->directed = directed;
    for (u = 0; u < kMaxVertex; u++) {
        for (v = 0; v < kMaxVertex; v++) {
            graph->edge_matrix[u][v] = graph->no_edge_value;
        }
    }
}

/* 算法7-1: 获取图的顶点个数 NumberOfVerts(graph) */
int NumberOfVerts(MGraph graph) {
    return graph->n_verts;
}
/* 算法7-1 结束 */

/* 算法7-2: 判断边是否存在  ExistEdge(graph, u, v) */
bool ExistEdge(MGraph graph, Vertex u, Vertex v) {
    bool ret = false;

    if (u < graph->n_verts && v < graph->n_verts) {
        if (u != v && graph->edge_matrix[u][v] != graph->no_edge_value) {
            ret = true;
        }
    }
    return ret;
}
/* 算法7-2 结束 */

/* 算法7-3: 找顶点的第一个邻接点  FirstAdjVert (graph,v) */
Vertex FirstAdjVert(MGraph graph, Vertex v) {
    Vertex u;

    for (u = 0; u < graph->n_verts; u++) {
        if (ExistEdge(graph, v, u) == true) {
            return u;
        }
    }
    return NIL;
}
/* 算法7-3 结束 */

/* 算法7-4: 向图中插入边 InsertEdge(graph, u,v,weight) */
void InsertEdge(MGraph graph, Vertex u, Vertex v, GElemSet weight) {
    if (ExistEdge(graph, u, v) == false) {
        graph->edge_matrix[u][v] = weight;
        graph->m_edges++;
        if (graph->directed == false) {
            graph->edge_matrix[v][u] = weight;
        }
    }
}
/* 算法7-4 结束 */

/* 算法7-5: 从图中删除边 RemoveEdge(graph, u,v) */
void RemoveEdge(MGraph graph, Vertex u, Vertex v) {
    if (ExistEdge(graph, u, v) == true) {
        graph->edge_matrix[u][v] = graph->no_edge_value;
        graph->m_edges--;
        if (graph->directed == false) {
            graph->edge_matrix[v][u] = graph->no_edge_value;
        }
    }
}
/* 算法7-5 结束 */

/* 算法7-6: 从图中删除顶点及所有邻接于该顶点的边 RemoveVert(graph,v) */
void RemoveVert(MGraph graph, Vertex v) {
    int n, count;
    Vertex u;

    n = graph->n_verts;
    if (v < 0 || v >= n) {
        printf("错误：待删除的顶点不存在。\n");
    } else {
        graph->ver_list[v] = graph->ver_list[n -
                                             1]; /* 用最后一个顶点信息覆盖v */
        count = 0; /* count计数由顶点v射出的边的条数 */
        for (u = 0; u < n; u++) {
            if (ExistEdge(graph, v, u) == true) {
                count++;
            }
        }
        if (graph->directed ==
                    true) { /* 有向图还要计数射入顶点v的边的条数 */
            for (u = 0; u < n; u++) {
                if (ExistEdge(graph, u, v) == true) {
                    count++;
                }
            }
        }
        for (u = 0; u < n; u++) { /* 将矩阵最后一行移入第v行 */
            graph->edge_matrix[v][u] = graph->edge_matrix[n - 1][u];
        }
        for (u = 0; u < n; u++) { /* 将矩阵最后一列移入第v列 */
            graph->edge_matrix[u][v] = graph->edge_matrix[u][n - 1];
        }
        graph->m_edges -= count; /* 更新边的条数 */
        graph->n_verts--; /* 更新顶点个数 */
    }
}
/* 算法7-6 结束 */